#ifndef STX_ALGORITHM_NEXT_PERMUTATION_HPP
#define STX_ALGORITHM_NEXT_PERMUTATION_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/swap.hpp>
#include <stx/algorithm/reverse.hpp>

namespace stx {

template <class Compare, class BidirectionalIterator>
inline bool
next_permutation_impl(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
{
    BidirectionalIterator i = last;
    if (first == last || first == --i) {
        return false;
    }
    while (1) {
        BidirectionalIterator ip1 = i;
        if (comp(*--i, *ip1)) {
            BidirectionalIterator j = last;
            while (!comp(*i, *--j)) {
            }
            swap(*i, *j);
            stx::reverse(ip1, last);
            return true;
        }
        if (i == first) {
            stx::reverse(first, last);
            return false;
        }
    }
}

template <class BidirectionalIterator, class Compare>
inline bool
next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    return next_permutation_impl<comp_ref>(first, last, comp);
}

template <class BidirectionalIterator>
inline bool
next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
    return stx::next_permutation(
        first,
        last,
        stx::less<typename std::iterator_traits<BidirectionalIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_NEXT_PERMUTATION_HPP
